package link

// ListNode 链表节点
type ListNode struct {
	Val  int
	Next *ListNode
}

// Reverse 反转链表
func Reverse(head *ListNode) *ListNode {
	var pre *ListNode
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}

// MiddleNode 求链表的中间节点
func MiddleNode(head *ListNode) *ListNode {
	fast, slow := head, head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}
	return slow
}

// 1->2->3->4
// next = head.Next
// head.Next = next.Next
// next.Next = head
// return next
// 1->3->4
// 2->1->3->4
// 2->1->4
// 2->1->4->3
// 2->1->4->3
func swapNode(head *LinkNode) *LinkNode {
	if head == nil || head.Next == nil {
		return head
	}
	next := head.Next
	head.Next = swapNode(next.Next)
	next.Next = head
	return next
}

// 1->2->3->4->5
// n = 3
// 3->4->5
// 1     4
// 2     5
// 3     null
func deleteDescIdx(head *LinkNode, n int) *LinkNode {
	var fast *LinkNode
	var next *LinkNode
	for i := 0; i < n; i++ {
		if fast == nil {
			fast = head
		} else {
			fast = fast.Next
		}
	}
	for fast.Next != nil {
		if next == nil {
			next = head
		} else {
			next = next.Next
		}
		fast = fast.Next
	}
	next.Next = next.Next.Next
	return head
}

func getCycleStart(head *LinkNode) int {
	fast, slow, start := head, head, head
	for fast != nil {
		fast = fast.Next.Next
		slow = slow.Next
		if fast.Val == slow.Val {
			break
		}
	}
	if fast == nil {
		return -1

	}
	pos := 0
	for start != nil {
		if start.Val == fast.Val {
			break
		}
		pos++
		start = start.Next
		fast = fast.Next
	}
	return pos
}
